/**
 * @filename SplayTree.h
 * @brief Splaytree
 * @author Sun Zehui <sunzehui18@outlook.com>
 * @version 1.0.0
 * @date 2021-11-24
 */

#ifndef __SPLAYTREEH__
#define __SPLAYTREEH__

#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
using namespace std;

template<typename Comparable>
class SplayTree;

/**
 * @brief BST_sort 普通的二叉树排序，没有经过随即shuffle
 *
 * @tparam Comparable 可比较对象
 * @param _data 待排数据r
 */
template<typename Comparable>
void Splay_BST_sort(vector<Comparable> &_data){
	SplayTree<Comparable> tree;
	for(auto iter=_data.begin(); iter!=_data.end(); ++iter){
		tree.insert(*iter);
	}

	_data.clear();
	tree.inorder(_data);
}

/**
 * @brief Randomized_BST_sort 随机的二叉树排序
 *
 * @tparam Comparable 可比较对象
 * @param _data 待排数据
 */
template<typename Comparable>
void Splay_Randomized_BST_sort(std::vector<Comparable> &_data){
	shuffle(_data.begin(), _data.end(), default_random_engine(2));
	SplayTree<Comparable> tree;
	for(auto iter=_data.begin(); iter!=_data.end(); ++iter){
		tree.insert(*iter);
	}

	_data.clear();
	tree.inorder(_data);
}

template <typename Comparable>
class SplayTree{
public:
    SplayTree():root(nullptr){}
	~SplayTree()
	{
		makeEmpty();
	}
	/**
	 * @brief insert 封装方法
	 *
	 * @param x Comparable&
	 */
	virtual void insert(const Comparable& x){
		insert(x, root);
	}
	virtual void insert(Comparable&& x){
		insert(std::move(x), root);
	}

	bool contains(const Comparable& x) {
		if(contains(x,root)==nullptr)
			return false;
		return true;
	}

	virtual void makeEmpty(){
		makeEmpty(root);
	}

	/**
	 * @brief printTree 中序输出
	 *
	 * @param out
	 */
	virtual void printTree(std::ostream &out = cout) const{
		printTree(root, out);
	}

	/**
	 * @brief inorder 中序遍历覆盖Vector
	 *
	 * @param vec Vector<Comparable>
	 */
	virtual void inorder(vector<Comparable>& vec){
		inorder(root, vec);
	}

	virtual void preorder(vector<Comparable>& vec){
		preorder(root, vec);
	}

	virtual void postorder(vector<Comparable>& vec){
		preorder(root, vec);
	}

	Comparable& getRootValue() const
	{
			return root->element;
	}

private:
    static const int ALLOWED_IMBALANCE = 1;

	struct SplayNode
	{
		Comparable element;
    	int height;
		SplayNode *left;
		SplayNode *right;
    	SplayNode(const Comparable & ele, SplayNode *lt, SplayNode *rt, int h=0)
        	:element(ele), left(lt), right(rt), height{h} {}
    	SplayNode(Comparable && ele, SplayNode *lt, SplayNode *rt, int h=0)
        	:element(ele), left(lt), right(rt), height{h} {}
	};

    SplayNode *root;

    /**
     * @brief contains same contain
     *
     * @param x value
     * @param t node
     *
     * @return node
     */
	SplayNode* contains(const Comparable& x, SplayNode *t){
		if( t == nullptr )
			return nullptr;
		else if( x < t->element )
			return contains( x, t->left );
		else if( t->element < x )
			return contains( x, t->right );
		else
			splay(t, root);
			return t;
	}

    int height(SplayNode * t) const
    {
        return t == nullptr ? -1 : t->height;
    }

    void insert(const Comparable& x, SplayNode* & t)
    {
        if(t==nullptr)
            t = new SplayNode{x, nullptr, nullptr};
        else if (x<t->element)
            insert(x, t->left);
        else if (t->element<x)
            insert(x,t->right);
    }

    /**
     * @brief splay splay 将某一节点进行推挤
     *
     * @param t 待推节点
     * @param node root
     */
    void splay(SplayNode* t, SplayNode* node)
    {
		if(node == nullptr || t==nullptr)
			return;
		if(t->element < node->element)
		{
			splay(t, node->left);
			rotateWithLeftChild(node);
		}
		else if(t->element > node->element)
		{
			splay(t, node->right);
			rotateWithRightChild(node);
		}
		else
			return;
		return;
    }

    void rotateWithLeftChild(SplayNode*& k2)
    {
        SplayNode *k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = max(height(k2->left), height(k2->right))+1;
        k1->height = max(height(k1->left), k2->height)+1;
        k2 = k1;
    }

	void rotateWithRightChild(SplayNode*& k2)
	{
		SplayNode* k1 = k2->right;
		k2->right = k1->left;
		k1->left = k2;
		k2->height = max(height(k2->left), height(k2->right))+1;
		k1->height = max(height(k1->right), k2->height)+1;
		k2 = k1;
	}

    void doubleWithLeftChild(SplayNode*& k3)
    {
        rotateWithRightChild(k3->left);
        rotateWithLeftChild(k3);
    }

	void doubleWithRightChild(SplayNode*& k3)
	{
		rotateWithLeftChild(k3->right);
		rotateWithRightChild(k3);
	}

	void makeEmpty(SplayNode* & t){
		if(t!=nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}

	/**
	 * @brief inorder 中序遍历的递归表达
	 *
	 * @param t 节点
	 * @param vec Vector<Comparable>
	 */
	void inorder(SplayNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			inorder(t->left, vec);
			vec.push_back(t->element);
			inorder(t->right, vec);
		}
	}

	void preorder(SplayNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			vec.push_back(t->element);
			inorder(t->left, vec);
			inorder(t->right, vec);
		}
	}

	void postorder(SplayNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			inorder(t->left, vec);
			inorder(t->right, vec);
			vec.push_back(t->element);
		}
	}

	void printTree(SplayNode* t, std::ostream& out) const{
		if( t!=nullptr ){
			printTree(t->left, out);
			out << t->element << "\t";
			printTree(t->right, out);
		}
		else
			; //Do nothing!
	}
};

#endif
